{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Shortest Subarray to be Removed to Make Array Sorted"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #array #two-pointers #binary-search #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #数组 #双指针 #二分查找 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findLengthOfShortestSubarray"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #删除最短的子数组使剩余数组有序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>arr</code>&nbsp;，请你删除一个子数组（可以为空），使得 <code>arr</code>&nbsp;中剩下的元素是 <strong>非递减</strong> 的。</p>\n",
    "\n",
    "<p>一个子数组指的是原数组中连续的一个子序列。</p>\n",
    "\n",
    "<p>请你返回满足题目要求的最短子数组的长度。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,2,3,10,4,2,3,5]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>我们需要删除的最短子数组是 [10,4,2] ，长度为 3 。剩余元素形成非递减数组 [1,2,3,3,5] 。\n",
    "另一个正确的解为删除子数组 [3,10,4] 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [5,4,3,2,1]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>由于数组是严格递减的，我们只能保留一个元素。所以我们需要删除长度为 4 的子数组，要么删除 [5,4,3,2]，要么删除 [4,3,2,1]。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1,2,3]\n",
    "<strong>输出：</strong>0\n",
    "<strong>解释：</strong>数组已经是非递减的了，我们不需要删除任何元素。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 4：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>arr = [1]\n",
    "<strong>输出：</strong>0\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= arr.length &lt;= 10^5</code></li>\n",
    "\t<li><code>0 &lt;= arr[i] &lt;= 10^9</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shortest-subarray-to-be-removed-to-make-array-sorted](https://leetcode.cn/problems/shortest-subarray-to-be-removed-to-make-array-sorted/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shortest-subarray-to-be-removed-to-make-array-sorted](https://leetcode.cn/problems/shortest-subarray-to-be-removed-to-make-array-sorted/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,10,4,2,3,5]', '[5,4,3,2,1]', '[1,2,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        right = n-1\n",
    "        while right and arr[right-1]<=arr[right]:\n",
    "            right -= 1\n",
    "        if right==0:\n",
    "            return 0\n",
    "        \n",
    "        ans = right\n",
    "        left= 0\n",
    "        while left==0 or arr[left-1]<=arr[left]:\n",
    "            while right<n and arr[left]>arr[right]:\n",
    "                right += 1\n",
    "            ans = min(ans, right-left-1)\n",
    "\n",
    "            left += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        right = n-1\n",
    "        while(right-1 >= 0 and arr[right-1] <= arr[right]):\n",
    "            right-=1\n",
    "        ans = right\n",
    "        if right==0:\n",
    "            return 0\n",
    "        for left, num in enumerate(arr):\n",
    "            if left==0 or arr[left]>=arr[left-1]:\n",
    "                right = max(left+1, right)\n",
    "                while(right < n and arr[right] < arr[left]):\n",
    "                    right+=1\n",
    "                ans = min(ans, right-left-1)\n",
    "            else:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "\n",
    "        n = len(arr)\n",
    "        i,j = 0,n-1\n",
    "        while i+1<=n-1 and arr[i+1]>=arr[i]:\n",
    "            i += 1\n",
    "        while j-1>=0 and arr[j]>=arr[j-1]:\n",
    "            j -= 1\n",
    "        print(i,j)\n",
    "        \n",
    "        if i >= j:\n",
    "            return(0)\n",
    "        \n",
    "        # i的右边全删除，或者j的左边全删除\n",
    "        res = min( n-(i+1), (j-1)-0+1 )\n",
    "        print( n-(i+1), (j-1)-0+1)\n",
    "        \n",
    "        R = j\n",
    "        for L in range(i+1):\n",
    "            while R < n and arr[R]<arr[L]:\n",
    "                R += 1\n",
    "            # 只删除 L到R的部分。L不删，R不删。所以是 L+1 到 R-1\n",
    "            res = min(res, (R-1)-(L+1)+1 )\n",
    "\n",
    "        return(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "      n = len(arr)\n",
    "      l = 0\n",
    "      r = n - 1\n",
    "      for i in range(1, n, 1):\n",
    "        if arr[l] <= arr[i]:\n",
    "          l = l + 1\n",
    "        else:\n",
    "          break\n",
    "      if l == n - 1:\n",
    "        return 0\n",
    "      for i in range(n - 2, -1, -1):\n",
    "        if arr[r] >= arr[i]:\n",
    "          r = r - 1\n",
    "        else:\n",
    "          break\n",
    "      tr = r\n",
    "      res = -inf\n",
    "      for tl in range(0, l + 1, 1):\n",
    "        while tr < n and arr[tl] > arr[tr]:\n",
    "          tr = tr + 1\n",
    "        res = max(res, tl + n - tr + 1)\n",
    "        if tr == n:\n",
    "          break\n",
    "      return n - max(l + 1, n - r, res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        i, j = 0, n - 1\n",
    "        while i + 1 < n and arr[i] <= arr[i + 1]:\n",
    "            i += 1\n",
    "        while j - 1 >= 0 and arr[j - 1] <= arr[j]:\n",
    "            j -= 1\n",
    "        if i >= j:\n",
    "            return 0\n",
    "        ans = min(n - i - 1, j)\n",
    "        for l in range(i + 1):\n",
    "            r = bisect_left(arr, arr[l], lo=j)\n",
    "            ans = min(ans, r - l - 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        i, j = 0, n - 1\n",
    "        while i + 1 < n and arr[i] <= arr[i + 1]:\n",
    "            i += 1\n",
    "        while j - 1 >= 0 and arr[j - 1] <= arr[j]:\n",
    "            j -= 1\n",
    "        if i >= j:\n",
    "            return 0\n",
    "        ans = min(n - i - 1, j)\n",
    "        for l in range(i + 1):\n",
    "            r = bisect_left(arr, arr[l], lo=j)\n",
    "            ans = min(ans, r - l - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        j = n - 1\n",
    "\n",
    "        while j > 0 and arr[j] >= arr[j-1]:\n",
    "            j -= 1\n",
    "        \n",
    "        if j == 0:\n",
    "            return j\n",
    "        res = j\n",
    "        \n",
    "        for i in range(n):\n",
    "            while j < n and arr[i] > arr[j] :\n",
    "                j += 1\n",
    "            print(i, j)\n",
    "            res = min(j - i - 1, res)\n",
    "\n",
    "            if i + 1 < n  and arr[i] > arr[i+1]:\n",
    "                break\n",
    "        \n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        i, j = 0, n - 1\n",
    "        while i + 1 < n and arr[i] <= arr[i + 1]:\n",
    "            i += 1\n",
    "        while j - 1 >= 0 and arr[j - 1] <= arr[j]:\n",
    "            j -= 1\n",
    "        if i >= j:\n",
    "            return 0\n",
    "        ans = min(n - i - 1, j)\n",
    "        r = j\n",
    "        for l in range(i + 1):\n",
    "            while r < n and arr[r] < arr[l]:\n",
    "                r += 1\n",
    "            ans = min(ans, r - l - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "      l = []\n",
    "      r = []\n",
    "      n = len(arr)\n",
    "      for i, x in enumerate(arr):\n",
    "        if not l or l[-1] <= x:\n",
    "          l.append(x)\n",
    "        else:\n",
    "          break\n",
    "      for i in range(n - 1, -1, -1):\n",
    "        x = arr[i]\n",
    "        if not r or r[0] >= x:\n",
    "          r.insert(0, x)\n",
    "        else:\n",
    "          break \n",
    "      if l == r:\n",
    "        return 0\n",
    "      ridx = 0\n",
    "      nl = len(l)\n",
    "      nr = len(r)\n",
    "      res = -inf\n",
    "      for i, x in enumerate(l):\n",
    "        while ridx < nr and x > r[ridx]:\n",
    "          ridx = ridx + 1\n",
    "        res = max(res, i + nr - ridx + 1)\n",
    "        if nr == ridx:\n",
    "          break\n",
    "      return n - max(nl, nr, res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        # 删除子数组，剩下为递增数组\n",
    "        # 滑动窗口\n",
    "        n = len(arr)\n",
    "        j = n-1\n",
    "        while j>0 and arr[j-1] <= arr[j]:\n",
    "            j -= 1\n",
    "        if j == 0:\n",
    "            return 0\n",
    "        print(j)\n",
    "        i = 0\n",
    "        res = j\n",
    "        # 双指针\n",
    "        while i<n:\n",
    "            while j<n and arr[j]<arr[i]:\n",
    "                 #右侧升序序列第一个值小于左侧值，此时j+1\n",
    "                 j += 1\n",
    "            res = min(res,j-i-1) #此时，ij都在升序序列中\n",
    "            if i+1<n and arr[i]>arr[i+1]: #不满足条件了,下一个i不满足条件了\n",
    "                break #一定要break\n",
    "            i += 1\n",
    "            \n",
    "        return res \n",
    "\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "\n",
    "\n",
    "\n",
    "        n = len(arr)\n",
    "        j = n - 1\n",
    "        while j > 0 and arr[j - 1] <= arr[j]:\n",
    "            j -= 1\n",
    "        \n",
    "        if j == 0:\n",
    "            return 0\n",
    "\n",
    "        res = j\n",
    "\n",
    "        for i in range(n):\n",
    "            while j < n and arr[j] < arr[i]:\n",
    "                j += 1\n",
    "            res = min(res, j - i - 1)\n",
    "            if i + 1 < n and arr[i] > arr[ i + 1]:\n",
    "                break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        y = n-1\n",
    "        while y>0 and arr[y]>=arr[y-1]:\n",
    "            y -= 1\n",
    "        if y==0:\n",
    "            return 0\n",
    "        res = y\n",
    "        for x in range(n):\n",
    "            while y<n and arr[y]<arr[x]:\n",
    "                y += 1\n",
    "            print(x, y)\n",
    "            res = min(res, y-x-1)\n",
    "            if x+1<n and arr[x]>arr[x+1]:\n",
    "                break\n",
    "\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        # 删除子数组使得有序\n",
    "        # 将数组分成三部分, 左中右\n",
    "        # 左边和右边为长度 [0,n]的有序子数组\n",
    "        # 先找左右的起点移动\n",
    "        n = len(arr)\n",
    "        left, right = 0, n - 1\n",
    "        while left < n - 1:\n",
    "            if arr[left] > arr[left + 1]:\n",
    "                break\n",
    "            left += 1\n",
    "        while right > 0:\n",
    "            if arr[right] < arr[right - 1]:\n",
    "                break\n",
    "            right -= 1\n",
    "        if right == 0 or left == n - 1:\n",
    "            return 0\n",
    "        ans = min(n - left - 1, right)\n",
    "        for i in range(left + 1):\n",
    "            # 在右边找最适合左边的\n",
    "            # 二分\n",
    "            l, r = right, n - 1\n",
    "            while l < r:\n",
    "                mid = l + r >> 1\n",
    "                if (arr[mid] < arr[i]):\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    r = mid\n",
    "            # print(i, l, arr[i], arr[l])\n",
    "            if (arr[l] >= arr[i]):\n",
    "                ans = min(ans, l - i - 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        left,right = 0,n-1\n",
    "        for i in range(n-1):\n",
    "            if arr[i+1] < arr[i]: break\n",
    "            left = i+1\n",
    "        if left == n-1: return 0\n",
    "        for i in range(n-1,0,-1):\n",
    "            if arr[i-1] > arr[i]: break\n",
    "            right = i-1\n",
    "        l = left\n",
    "        ans = min(n-1-left,right)\n",
    "        for r in range(n-1,right-1,-1):\n",
    "            while l>=0 and arr[l] > arr[r]: l -= 1\n",
    "            if l == -1: break\n",
    "            ans = min(ans,r-l-1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "\n",
    "\n",
    "\n",
    "        n = len(arr)\n",
    "        j = n - 1\n",
    "        while j > 0 and arr[j - 1] <= arr[j]:\n",
    "            j -= 1\n",
    "        \n",
    "        if j == 0:\n",
    "            return 0\n",
    "\n",
    "        res = j\n",
    "\n",
    "        for i in range(n):\n",
    "            while j < n and arr[j] < arr[i]:\n",
    "                j += 1\n",
    "            res = min(res, j - i - 1)\n",
    "            if i + 1 < n and arr[i] > arr[ i + 1]:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        if arr == sorted(arr):\n",
    "            return 0\n",
    "        else:\n",
    "            l, r = 0, len(arr) - 1\n",
    "        # 从左到右找第一个降序的位置\n",
    "            while (l < len(arr) - 1 and arr[l] <= arr[l + 1]):\n",
    "                l += 1\n",
    "        # 从右往左找第一个升序的位置\n",
    "            while (r > 0 and arr[r] >= arr[r-1]):\n",
    "                r -= 1\n",
    "        # 找到中间符合升序的空间\n",
    "            if(arr[l]<= arr[r]):\n",
    "                return r-l-1\n",
    "            tmp1 = arr.copy()\n",
    "            del tmp1[l:r]\n",
    "            # print(tmp1)\n",
    "            lsum = Solution.findLengthOfShortestSubarray(self,tmp1)\n",
    "            # print(lsum)\n",
    "            tmp2 = arr.copy()\n",
    "            del tmp2[l+1:r+1]\n",
    "            # print(tmp2)\n",
    "            rsum = Solution.findLengthOfShortestSubarray(self,tmp2)\n",
    "            # print(rsum)\n",
    "            return min(lsum, rsum) + r-l\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        right = n-1\n",
    "        while(right-1 >= 0 and arr[right-1] <= arr[right]):\n",
    "            right-=1\n",
    "        ans = right\n",
    "        if right==0:\n",
    "            return 0\n",
    "        for left, num in enumerate(arr):\n",
    "            if left==0 or arr[left]>=arr[left-1]:\n",
    "                while(right < n and arr[right] < arr[left]):\n",
    "                    right+=1\n",
    "                ans = min(ans, right-left-1)\n",
    "            else:\n",
    "                break\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)        # 获取数组长度\n",
    "        j = n - 1           # 初始化最长非递减后缀数组右端点\n",
    "        # 查找最长非递减后缀数组右端点\n",
    "        while j > 0 and arr[j-1] <= arr[j]:\n",
    "            j -= 1\n",
    "        # 右端点到达整个数组起点，整个数组都满足非递减，无需删除子数组\n",
    "        if j == 0:\n",
    "            return 0\n",
    "        res = j     # 初始认为子数组就是后缀数组以外的内容，长度为j\n",
    "        # 查找每一个前缀数组下标i可匹配的最小后缀数组下标j\n",
    "        for i in range(n):\n",
    "            while j < n and arr[j] < arr[i]:\n",
    "                j += 1\n",
    "            # 更新最小子数组长度\n",
    "            res = min(res, j - i - 1)\n",
    "            # 下一个元素和当前元素不满足非递减条件 到达最长非递减前缀数组边界\n",
    "            if i != n - 1 and arr[i + 1] < arr[i]:\n",
    "                break\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        r = n - 1\n",
    "        while r > 0 and arr[r-1] <= arr[r]:\n",
    "            r -= 1\n",
    "        if not r:\n",
    "            return r\n",
    "        res = r\n",
    "        l = 0\n",
    "        while l == 0 or arr[l-1] <= arr[l]:\n",
    "            while r < n and arr[l] > arr[r]:\n",
    "                r += 1\n",
    "            res = min(res, r-l-1)\n",
    "            l += 1\n",
    "        return res \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        l, r = 0, n - 1\n",
    "        while l < n - 1 and arr[l] <= arr[l + 1]: l += 1\n",
    "        while r > 0 and arr[r - 1] <= arr[r]: r -= 1\n",
    "        if l >= r: return 0\n",
    "        i, j = 0, r\n",
    "        res = inf\n",
    "        for j in range(r, n):\n",
    "            while i <= l and arr[i] <= arr[j]: i += 1\n",
    "            res = min(res, j - i)\n",
    "        # 需要额外考虑r==n的情况\n",
    "        return min(res,n-1-l,r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        r = n - 1\n",
    "        while r and arr[r - 1] <= arr[r]:\n",
    "            r -= 1\n",
    "        if r == 0: \n",
    "            return 0\n",
    "        ans = r  \n",
    "        left = 0  \n",
    "        while left == 0 or arr[left - 1] <= arr[left]:\n",
    "            while r < n and arr[r] < arr[left]:\n",
    "                r += 1\n",
    "            ans = min(ans, r - left - 1)\n",
    "            left += 1\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        pre = [False] * n\n",
    "        pre[0] = True\n",
    "        for i in range(1, n):\n",
    "            if arr[i] >= arr[i-1]:\n",
    "                pre[i] = True\n",
    "            else:\n",
    "                break\n",
    "        \n",
    "        suf = [False] * n\n",
    "        suf[-1] = True\n",
    "        ans = n-1\n",
    "        for i in range(n-2, -1, -1):\n",
    "            if arr[i] <= arr[i+1]:\n",
    "                suf[i] = True\n",
    "                ans = i\n",
    "            else:\n",
    "                break\n",
    "        right = 0\n",
    "        for left, s in enumerate(pre):\n",
    "            if not s:\n",
    "                break\n",
    "            right = max(left+1, right)\n",
    "            while(right < n and (suf[right]==False or arr[right] < arr[left])):\n",
    "                right+=1\n",
    "            ans = min(ans, right-left-1)\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        hi = len(arr) - 1\n",
    "        while hi > 0 and arr[hi-1] <= arr[hi]:\n",
    "            hi -= 1\n",
    "        if hi == 0:\n",
    "            return 0\n",
    "        result = hi\n",
    "        for i in range(len(arr)):\n",
    "            while hi < len(arr) and arr[i] > arr[hi]:\n",
    "                hi += 1\n",
    "            result = min(result, hi - i - 1)\n",
    "            if i + 1 < len(arr) and arr[i] > arr[i + 1]:\n",
    "                break\n",
    "        return result\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "\n",
    "        n = len(arr)\n",
    "        d = {}\n",
    "\n",
    "        # 1,2,3,10,4,8,5\n",
    "\n",
    "        l = n\n",
    "        for i in range(1, n):\n",
    "            if arr[i] < arr[i-1]:\n",
    "                l = i\n",
    "                break\n",
    "\n",
    "\n",
    "        st = [(inf, n)]\n",
    "        for i in range(n-1, l, -1):\n",
    "\n",
    "            if arr[i] <= st[-1][0]:\n",
    "                if arr[i] == st[-1][0]:\n",
    "                    st[-1][1] = i\n",
    "                else:\n",
    "                    st.append([arr[i], i])\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        #print(f'{st} {l}')\n",
    "        ret = st[-1][1]\n",
    "        for i in range(l):\n",
    "            while st[-1][0] < arr[i]:\n",
    "                st.pop()\n",
    "            \n",
    "            delete_num = st[-1][1] - 1 - i\n",
    "            #print(f'{st} {delete_num}')\n",
    "            ret = min(ret, delete_num)\n",
    "        \n",
    "        return ret\n",
    "\n",
    "        # the solution is very ugly\n",
    "        # 1. find the increase arr from left\n",
    "        # 2. find the decrease arr from right\n",
    "        # for each i in left to check the corresponding pos in right\n",
    "        # special case is delete all left and the answer is n - len(right)\n",
    "        # another tricky part is that same value in right, override the index of same value\n",
    "        # may use bisect to speed up\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        right = n - 1\n",
    "        while right and arr[right - 1] <= arr[right]:\n",
    "            right -= 1\n",
    "        if right == 0:  # arr 已经是非递减数组\n",
    "            return 0\n",
    "        # 此时 arr[right-1] > arr[right]\n",
    "        ans = right  # 删除 arr[:right]\n",
    "        left = 0  # 枚举 left\n",
    "        while left == 0 or arr[left - 1] <= arr[left]:\n",
    "            while right < n and arr[right] < arr[left]:\n",
    "                right += 1\n",
    "            # 此时 arr[left] <= arr[right]，删除 arr[left+1:right]\n",
    "            ans = min(ans, right - left - 1)\n",
    "            left += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        if n < 2:\n",
    "            return 0\n",
    "        left, right = 0, n - 1\n",
    "        while right - 1 >= 0 and arr[right] >= arr[right - 1]:\n",
    "            right -= 1\n",
    "        if right == 0:\n",
    "            return 0\n",
    "        max_len = n - right\n",
    "        while right <= n:\n",
    "            while right == n or arr[left] <= arr[right]:\n",
    "                if arr[left] <= arr[left + 1]:\n",
    "                    left += 1\n",
    "                else:\n",
    "                    max_len = max(max_len, n - right + left + 1)\n",
    "                    return n - max_len\n",
    "            max_len = max(max_len, n - right + left)\n",
    "            right += 1\n",
    "        return n - max_len\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        right = n-1\n",
    "        ans =0\n",
    "        while right and arr[right-1]<=arr[right]:\n",
    "            right-=1\n",
    "        if right ==0:\n",
    "            return 0\n",
    "        ans =right  #去掉开头的子数组（即末尾的子数组是非递减）\n",
    "        left = 0\n",
    "        while True:\n",
    "        #去掉中间的子数组，即开头跟末尾可以组成一个递增（非递减）序列（固定右端点，再固定左端点）(考虑去掉末尾的子数组)\n",
    "            while right==n or arr[left]<=arr[right]:\n",
    "                ans =min(ans,right-left-1)\n",
    "                if arr[left] >arr[left+1]:\n",
    "                    return ans\n",
    "                left+=1\n",
    "            right+=1\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        i, j = 0, n - 1\n",
    "        while i < j and arr[i+1] >= arr[i]:\n",
    "            i += 1\n",
    "        while i < j and arr[j-1] <= arr[j]:\n",
    "            j -= 1\n",
    "\n",
    "\n",
    "        res = min(n - i - 1, j)\n",
    "\n",
    "        for ti in range(i, -1, -1):\n",
    "            tj = j\n",
    "            while tj < n and arr[ti] > arr[tj]:\n",
    "                tj += 1\n",
    "            res = min(res, tj - ti - 1)\n",
    "        return max(res, 0)\n",
    "\n",
    "            \n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "\n",
    "        if n <= 1:\n",
    "            return 0\n",
    "\n",
    "        # 查找左边递增序列的索引范围\n",
    "        left_start = 0\n",
    "        left_end = n - 1\n",
    "        for i in range(1, n):\n",
    "            if arr[i] >= arr[i - 1]:\n",
    "                continue\n",
    "            else:\n",
    "                left_end = i - 1\n",
    "                break\n",
    "        if left_end == n - 1:\n",
    "            # 已经是非递减了\n",
    "            return 0\n",
    "        elif left_end == n - 2:\n",
    "            # 只差1个\n",
    "            return 1\n",
    "        \n",
    "        # 查找右边递增序列的索引范围\n",
    "        right_end = n - 1\n",
    "        right_start = left_end + 1\n",
    "        for i in range(n-2, left_end, -1):\n",
    "            if arr[i] <= arr[i + 1]:\n",
    "                continue\n",
    "            else:\n",
    "                right_start = i + 1\n",
    "                break\n",
    "        if right_start == 1:\n",
    "            # 只差1个\n",
    "            return 1\n",
    "\n",
    "        if arr[left_end] <= arr[right_start]:\n",
    "            # 只需移除中间的\n",
    "            return right_start - left_end - 1\n",
    "        elif arr[left_start] > arr[right_end]:\n",
    "            return n - max(left_end - left_start + 1, right_end - right_start + 1)\n",
    "\n",
    "        \n",
    "        # 剩下情况如下     rightend\n",
    "        #  leftend        /\n",
    "        #    /           /\n",
    "        #   /           /\n",
    "        #  /            rightstart\n",
    "        # leftstart    \n",
    "        result = n - (right_end - right_start + 1)  # 左边序列都不保留时\n",
    "        left_index = left_start\n",
    "        right_index = right_start\n",
    "        while left_index <= left_end:\n",
    "            # 左边保留到 left_index 时\n",
    "            while right_index <= right_end and arr[left_index] > arr[right_index]:\n",
    "                right_index += 1\n",
    "            \n",
    "            r = right_index - left_index - 1\n",
    "            if r < result:\n",
    "                result = r\n",
    "                \n",
    "            left_index += 1\n",
    "        return result\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        j = n - 1\n",
    "        while j > 0 and arr[j - 1] <= arr[j]:\n",
    "            j -= 1\n",
    "        if j == 0:\n",
    "            return 0\n",
    "        res = j\n",
    "        for i in range(n):\n",
    "            while j < n and arr[j] < arr[i]:\n",
    "                j += 1\n",
    "            res = min(res, j - i - 1)\n",
    "            if i + 1 < n and arr[i] > arr[i + 1]:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "# class Solution:\n",
    "#     def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        r = n - 1\n",
    "        while r > 0:\n",
    "            if arr[r] < arr[r - 1]:\n",
    "                break\n",
    "            r -= 1\n",
    "        if r == 0:  # arr 已经是非递减数组\n",
    "            return 0\n",
    "        # 此时 arr[right-1] > arr[right]\n",
    "        res = r  # 删除 arr[:right]\n",
    "        l = 0  # 枚举 left\n",
    "        while l == 0 or arr[l - 1] <= arr[l]:\n",
    "            while r < n and arr[r] < arr[l]:\n",
    "                r += 1\n",
    "            # 此时 arr[left] <= arr[right]，删除 arr[left+1:right]\n",
    "            res = min(res, r - l - 1)\n",
    "            l += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        right = n - 1\n",
    "        while right and arr[right - 1] <= arr[right]:\n",
    "            right -= 1\n",
    "        if right == 0:  # arr 已经是非递减数组\n",
    "            return 0\n",
    "        # 此时 arr[right-1] > arr[right]\n",
    "        ans = right  # 删除 arr[:right]\n",
    "        left = 0  # 枚举 left\n",
    "        while left == 0 or arr[left - 1] <= arr[left]:\n",
    "            while right < n and arr[right] < arr[left]:\n",
    "                right += 1\n",
    "            # 此时 arr[left] <= arr[right]，删除 arr[left+1:right]\n",
    "            ans = min(ans, right - left - 1)\n",
    "            left += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        i = n-1\n",
    "        while i and arr[i-1] <= arr[i]:\n",
    "            i-=1\n",
    "        if not i: return 0\n",
    "        r = i\n",
    "        j = 0\n",
    "        while j==0 or arr[j-1]<=arr[j]:\n",
    "            while i<n and arr[i]<arr[j]:\n",
    "                i+=1\n",
    "            r = min(r,i-j-1)\n",
    "            j+=1\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        i, j = 0, n - 1\n",
    "        while i + 1 < n and arr[i] <= arr[i + 1]:\n",
    "            i += 1\n",
    "        while j - 1 >= 0 and arr[j - 1] <= arr[j]:\n",
    "            j -= 1\n",
    "        if i >= j:\n",
    "            return 0\n",
    "        ans = min(n - i - 1, j)\n",
    "        for l in range(i + 1):\n",
    "            r = bisect_left(arr, arr[l], lo=j)\n",
    "            ans = min(ans, r - l - 1)\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        j = n - 1\n",
    "        while j > 0 and arr[j-1] <= arr[j]:\n",
    "            j -= 1\n",
    "        if j == 0:\n",
    "            return 0\n",
    "        res = j\n",
    "        for i in range(n):\n",
    "            while j < n and arr[j] < arr[i]:\n",
    "                j += 1\n",
    "            res = min(res, j - i - 1)\n",
    "            if i + 1 < n and arr[i] > arr[i+1]:\n",
    "                break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        j = n - 1\n",
    "        while j > 0 and arr[j - 1] <= arr[j]:\n",
    "            j -= 1\n",
    "        if j == 0:\n",
    "            return 0\n",
    "        res = j\n",
    "        for i in range(n):\n",
    "            while j < n and arr[j] < arr[i]:\n",
    "                j += 1\n",
    "            res = min(res, j - i - 1)\n",
    "            if i + 1 < n and arr[i] > arr[i + 1]:\n",
    "                break\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        \"\"\"滑动窗口\n",
    "        \"\"\"\n",
    "        n = len(arr)\n",
    "        right = n - 1\n",
    "        while right > 0:\n",
    "            if arr[right] < arr[right - 1]:\n",
    "                break\n",
    "            right -= 1\n",
    "        if right == 0:\n",
    "            return 0\n",
    "        ans = right\n",
    "        # 枚举最左边来移动删除窗口的右边界\n",
    "        for left, x in enumerate(arr):\n",
    "            if left != 0 and arr[left] < arr[left - 1]:\n",
    "                break\n",
    "            # 右边界必须大于左边\n",
    "            while right < n and arr[left] > arr[right]:\n",
    "                right += 1\n",
    "            ans = min(ans, right - left - 1)\n",
    "            left += 1\n",
    "        return ans\n",
    "        \"\"\" 二分O(nlogn)\n",
    "        # 删除子数组使得有序\n",
    "        # 将数组分成三部分, 左中右\n",
    "        # 左边和右边为长度 [0,n]的有序子数组\n",
    "        # 先找左右的起点移动\n",
    "        n = len(arr)\n",
    "        left, right = 0, n - 1\n",
    "        while left < n - 1:\n",
    "            if arr[left] > arr[left + 1]:\n",
    "                break\n",
    "            left += 1\n",
    "        while right > 0:\n",
    "            if arr[right] < arr[right - 1]:\n",
    "                break\n",
    "            right -= 1\n",
    "        if right == 0 or left == n - 1:\n",
    "            return 0\n",
    "        ans = min(n - left - 1, right)\n",
    "        for i in range(left + 1):\n",
    "            # 在右边找最适合左边的\n",
    "            # 二分\n",
    "            l, r = right, n - 1\n",
    "            while l < r:\n",
    "                mid = l + r >> 1\n",
    "                if (arr[mid] < arr[i]):\n",
    "                    l = mid + 1\n",
    "                else:\n",
    "                    r = mid\n",
    "            # print(i, l, arr[i], arr[l])\n",
    "            if (arr[l] >= arr[i]):\n",
    "                ans = min(ans, l - i - 1)\n",
    "        return ans\n",
    "        \"\"\"\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        right = n - 1\n",
    "        while right and arr[right - 1] <= arr[right]: right -= 1\n",
    "        if right == 0: return 0\n",
    "\n",
    "        min_del_cnt, left = right, 0\n",
    "        while True:\n",
    "            while right < n and arr[left] > arr[right]: right += 1\n",
    "            min_del_cnt = min(min_del_cnt, right - left - 1)\n",
    "            if left + 1 < n and  arr[left] <= arr[left + 1]:\n",
    "                left += 1\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return min_del_cnt\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        l, r = 0, n - 1\n",
    "        while l < n - 1 and arr[l] <= arr[l + 1]: l += 1\n",
    "        while r > 0 and arr[r - 1] <= arr[r]: r -= 1\n",
    "        if l >= r: return 0\n",
    "        i, j = 0, r\n",
    "        res = inf\n",
    "        for j in range(r, n):\n",
    "            while i <= l and arr[i] <= arr[j]: i += 1\n",
    "            res = min(res, j - i)\n",
    "        # 需要额外考虑r==n的情况\n",
    "        return min(res,n-1-l,r)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        tot=[]\n",
    "        for i in range(n-1):\n",
    "            if arr[i]>arr[i+1]:\n",
    "                tot.append(i+1)\n",
    "        if not tot:\n",
    "            return 0\n",
    "        ans=tot[-1]-tot[0]\n",
    "        if tot[0]!=0:\n",
    "            x=tot[0]-1\n",
    "        else:\n",
    "            return ans\n",
    "        y=tot[-1]\n",
    "        if arr[x]<=arr[y]:\n",
    "            return ans\n",
    "        p=0\n",
    "        q=1\n",
    "        while y+p<n and arr[x]>arr[y+p]:\n",
    "            p+=1\n",
    "        t=p\n",
    "        if y+p==n:\n",
    "            p-=1\n",
    "        while x>=q and p>-1:\n",
    "            while x>=q and p>-1 and arr[x-q]<=arr[y+p]:\n",
    "                p-=1\n",
    "            if p+q+1<t:\n",
    "                t=p+q+1\n",
    "            if p>t:\n",
    "                break\n",
    "            q+=1\n",
    "        t=min(t,x+1)\n",
    "        return t+ans\n",
    "            \n",
    "\n",
    "\n",
    "        \n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        j = n - 1\n",
    "        while j > 0 and arr[j] >= arr[j-1]:\n",
    "            j -= 1\n",
    "        if j == 0:\n",
    "            return 0\n",
    "        res = j\n",
    "        for i in range(n):\n",
    "            while j < n and arr[j] < arr[i]:\n",
    "                j += 1\n",
    "            res = min(res, j - i - 1)\n",
    "            if i + 1 < n and arr[i+1] < arr[i]:\n",
    "                break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        right = n - 1\n",
    "        while right and arr[right - 1] <= arr[right]: right -= 1\n",
    "        if right == 0: return 0\n",
    "\n",
    "        min_del_cnt, left = right, 0\n",
    "        while left == 0 or arr[left - 1] <= arr[left]:\n",
    "            while right < n and arr[left] > arr[right]: right += 1\n",
    "            min_del_cnt = min(min_del_cnt, right - left - 1)\n",
    "            left += 1\n",
    "\n",
    "        return min_del_cnt\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        right = n - 1\n",
    "        while right and arr[right - 1] <= arr[right]:\n",
    "            right -= 1\n",
    "        if right == 0:  # arr 已经是非递减数组\n",
    "            return 0\n",
    "        # 此时 arr[right-1] > arr[right]\n",
    "        ans = right  # 删除 arr[:right]\n",
    "        left = 0  # 枚举 left\n",
    "        while left == 0 or arr[left - 1] <= arr[left]:\n",
    "            while right < n and arr[right] < arr[left]:\n",
    "                right += 1\n",
    "            # 此时 arr[left] <= arr[right]，删除 arr[left+1:right]\n",
    "            ans = min(ans, right - left - 1)\n",
    "            left += 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        right = n - 1\n",
    "        while right and arr[right - 1] <= arr[right]:\n",
    "            right -= 1\n",
    "        if right == 0:  # arr 已经是非递减数组\n",
    "            return 0\n",
    "        # 此时 arr[right-1] > arr[right]\n",
    "        ans = right  # 删除 arr[:right]\n",
    "        left = 0  # 枚举 left\n",
    "        while left == 0 or arr[left - 1] <= arr[left]:\n",
    "            while right < n and arr[right] < arr[left]:\n",
    "                right += 1\n",
    "            # 此时 arr[left] <= arr[right]，删除 arr[left+1:right]\n",
    "            ans = min(ans, right - left - 1)\n",
    "            left += 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        index1,index2 = 0,len(arr)-1\n",
    "        while index1 < len(arr)-1:\n",
    "            if arr[index1+1] >= arr[index1]:\n",
    "                index1 += 1\n",
    "            else:\n",
    "                break\n",
    "        while index2 > 0:\n",
    "            if arr[index2-1] <= arr[index2]:\n",
    "                index2 -= 1\n",
    "            else:\n",
    "                break\n",
    "        res = min(len(arr)-index1-1,index2)\n",
    "        i,j = 0,index2\n",
    "        while i<=index1 and j<len(arr):\n",
    "            if arr[j] < arr[i]:\n",
    "                j += 1\n",
    "            else:\n",
    "                res = min(res,max(j-i-1,0))\n",
    "                i += 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        r = n - 1\n",
    "        while r > 0:\n",
    "            if arr[r] < arr[r - 1]:\n",
    "                break\n",
    "            r -= 1\n",
    "        if r == 0:\n",
    "            return 0\n",
    "        res = r\n",
    "        l = 0\n",
    "        while l == 0 or arr[l - 1] <= arr[l]:\n",
    "            while r < n and arr[r] < arr[l]:\n",
    "                r += 1\n",
    "\n",
    "            res = min(res, r - l - 1)\n",
    "            l += 1\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        r = n - 1\n",
    "        while r and arr[r - 1] <= arr[r]:\n",
    "            r -= 1\n",
    "        if r == 0: \n",
    "            return 0\n",
    "        ans = r  \n",
    "        l = 0  \n",
    "        while l == 0 or arr[l - 1] <= arr[l]:\n",
    "            while r < n and arr[r] < arr[l]:\n",
    "                r += 1\n",
    "            ans = min(ans, r - l - 1)\n",
    "            l += 1\n",
    "        return ans\n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        result = n\n",
    "        #删后\n",
    "        left = n-1\n",
    "        flag = False\n",
    "        for i in range(1,n):\n",
    "            if(arr[i-1] > arr[i]):\n",
    "                flag = True\n",
    "                break\n",
    "        if(flag):\n",
    "            left = i - 1\n",
    "        result = min(result, n - left - 1)\n",
    "        #删前\n",
    "        right = 0\n",
    "        flag = False\n",
    "        for i in range(n-1,0,-1):\n",
    "            if(arr[i-1] > arr[i]):\n",
    "                flag = True\n",
    "                break\n",
    "        if(flag):\n",
    "            right = i\n",
    "        result = min(result, right)\n",
    "        j = right\n",
    "        for i in range(left+1):\n",
    "            while(j <= i or (j <= n- 1 and arr[j] < arr[i])):\n",
    "                j += 1\n",
    "            if(j < n):\n",
    "                result = min(result, j-i-1)\n",
    "        return result\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        \n",
    "        \"\"\" \n",
    "        (left,right)表示需要删除的子数组区间\n",
    "        \"\"\"\n",
    "        n = len(arr)\n",
    "        right = n-1\n",
    "        while right and arr[right-1] <=arr[right]:\n",
    "            right-=1\n",
    "        if(right == 0): # 这里表示数组本身就是递增的\n",
    "            return 0\n",
    "        result = right # 表示删除right左侧所有的\n",
    "        left = 0\n",
    "        while left==0 or arr[left-1]<=arr[left]: # 从左侧开始枚举\n",
    "            while right<n and arr[left] > arr[right]:\n",
    "                right+=1\n",
    "            result = min(result, right-left-1)\n",
    "            left+=1\n",
    "        return result\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        right = n - 1\n",
    "        while right and arr[right-1] <= arr[right]:\n",
    "            right -= 1\n",
    "        if right == 0:\n",
    "            return 0\n",
    "        \n",
    "        ans = right\n",
    "        left = 0\n",
    "        while left == 0 or arr[left-1] <= arr[left]:\n",
    "            while right < n and arr[right] < arr[left]:\n",
    "                right += 1\n",
    "            ans = min(ans,right-left-1)\n",
    "            left += 1\n",
    "        return ans\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        # p q 分别为第一个/最后一个 递减/递增 的极值点下标\n",
    "        p, q = -1, -1\n",
    "        n = len(arr)\n",
    "        for i in range(1, n):\n",
    "            if arr[i] < arr[i - 1]:\n",
    "                p = i - 1\n",
    "                break\n",
    "        if p == -1: return 0\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            if arr[i] > arr[i + 1]:\n",
    "                q = i + 1\n",
    "                break        \n",
    "        # 首先去掉中间一定会去掉的节点，即去除长度为：p - q - 1\n",
    "        left_arr, right_arr = arr[:p + 1], arr[q:]\n",
    "\n",
    "        n_left, n_right = len(left_arr), len(right_arr)\n",
    "        min_length = inf\n",
    "        for i in range(n_left - 1, -1, -1):\n",
    "            min_length = min(min_length, bisect_left(right_arr, left_arr[i]) + n_left - 1 - i)\n",
    "        \n",
    "        for i in range(n_right):\n",
    "            min_length = min(min_length, n_left - bisect_right(left_arr, right_arr[i]) + i)\n",
    "\n",
    "        return min_length + q - p - 1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        j = n - 1\n",
    "        while j > 0 and arr[j - 1] <= arr[j]:\n",
    "            j -= 1\n",
    "        if j == 0:\n",
    "            return 0\n",
    "        res = j\n",
    "        for i in range(n):\n",
    "            while j < n and arr[j] < arr[i]:\n",
    "                j += 1\n",
    "            res = min(res, j - i - 1)\n",
    "            if i + 1 < n and arr[i] > arr[i + 1]:\n",
    "                break\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        right = n-1\n",
    "        while right>0 and arr[right-1]<=arr[right]:\n",
    "            right -= 1\n",
    "        if right == 0:\n",
    "            return 0\n",
    "        ans = right\n",
    "        left = 0\n",
    "        while left==0 or arr[left-1]<=arr[left]:\n",
    "            while right<n and arr[right]<arr[left]:\n",
    "                right += 1\n",
    "            ans = min(ans, right - left - 1)\n",
    "            left += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        \"\"\"\n",
    "        双指针：(left,right)是要删除的子数组范围 \n",
    "        首先要找到right的起始位置 right需要满足就是right后面的元素是非递减的\n",
    "        随后枚举left 需要保证arr[left]<=arr[right]\n",
    "        问题解决\n",
    "        Q1为啥新的left不会左移right\n",
    "        因为right之前必定小于left\n",
    "        \"\"\"\n",
    "        n = len(arr)\n",
    "        right = n-1\n",
    "        while right and arr[right-1]<=arr[right]:\n",
    "            right -= 1\n",
    "        if right == 0: #整个数组都是非递减的\n",
    "            return 0\n",
    "        # 此时right后面都是递减的 但arr[right-1] > arr[right]\n",
    "        left = 0 # 枚举 left\n",
    "        rs = right #删除[:right]\n",
    "        while left==0 or arr[left-1]<=arr[left]:\n",
    "            while right<n and arr[right]<arr[left]:\n",
    "                right += 1\n",
    "            rs = min(rs,right-left-1)\n",
    "            left += 1\n",
    "        return rs\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        left, right = 0, n - 1\n",
    "        while left + 1 < n:\n",
    "            if arr[left] <= arr[left + 1]:\n",
    "                left += 1\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        while right - 1 >= 0:\n",
    "            if arr[right] >= arr[right - 1]:\n",
    "                right -= 1\n",
    "            else:\n",
    "                break\n",
    "        if left == n-1:\n",
    "            return 0\n",
    "            \n",
    "        ans = ans = min(n - left, right)\n",
    "        while left >= 0:\n",
    "            r = bisect.bisect_left(arr[right:], arr[left])\n",
    "            ans = min(ans, right + r - left - 1)\n",
    "            left -= 1\n",
    "        return max(ans, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        left_idx = -1; right_idx = n\n",
    "        for idx in range(1, n):\n",
    "            if arr[idx] < arr[idx-1]:\n",
    "                left_idx = idx\n",
    "                break\n",
    "        if left_idx == -1:\n",
    "            return 0\n",
    "\n",
    "        max_l = left_idx\n",
    "        for idx in range(n-2, -1, -1):\n",
    "            if arr[idx] > arr[idx+1]:\n",
    "                right_idx = idx + 1\n",
    "                break\n",
    "        \n",
    "        max_l = max(max_l, n - right_idx)\n",
    "        def binary(arr, start, target):\n",
    "            left, right = start, len(arr) - 1\n",
    "            while left <= right:\n",
    "                mid = left + (right-left) // 2\n",
    "                if arr[mid] >= target:\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            return left\n",
    "\n",
    "        ans = float(\"inf\")\n",
    "        for i in range(left_idx):\n",
    "            idx = binary(arr, right_idx, arr[i])\n",
    "            max_l = max(max_l, n - (idx - i - 1))\n",
    "        return n - max_l\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        j = n - 1\n",
    "        while j > 0 and arr[j - 1] <= arr[j]:\n",
    "            j -= 1\n",
    "        if j == 0:\n",
    "            return 0\n",
    "        res = j\n",
    "        for i in range(n):\n",
    "            while j < n and arr[j] < arr[i]:\n",
    "                j += 1\n",
    "            res = min(res, j - i - 1)\n",
    "            if i + 1 < n and arr[i] > arr[i + 1]:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        j = n - 1\n",
    "        while j > 0 and arr[j] >= arr[j - 1]:\n",
    "            j -= 1\n",
    "        if j == 0:\n",
    "            return 0\n",
    "        #先假设需要全部删除再通过左指针维护\n",
    "        ans = j\n",
    "        for i in range(n):  \n",
    "            #判断左侧末尾与右侧首大小关系是否需要扩展区间\n",
    "            while j < n and arr[j] < arr[i]:\n",
    "                j += 1\n",
    "            ans = min(ans, j - i - 1)\n",
    "            if i + 1 < n and arr[i] > arr[i+1]:\n",
    "                break\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        if n == 1:\n",
    "            return 0\n",
    "\n",
    "        left_bound, right_bound = 0, n - 1\n",
    "        while left_bound < n-1 and arr[left_bound] <= arr[left_bound+1]:\n",
    "            left_bound += 1    \n",
    "        \n",
    "        while right_bound > 0 and arr[right_bound-1] <= arr[right_bound]:\n",
    "            right_bound -= 1\n",
    "        \n",
    "        if right_bound == 0:\n",
    "            return 0\n",
    "\n",
    "        res = min(right_bound, n-left_bound-1)\n",
    "\n",
    "        left, right = 0, right_bound\n",
    "        \n",
    "        while left <= left_bound:\n",
    "            while right < n and arr[left] > arr[right]:\n",
    "                right += 1\n",
    "            res = min(res, right - left - 1)\n",
    "            left += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, A: List[int]) -> int:\n",
    "        N = len(A)\n",
    "        l, r = 0, N-1\n",
    "        while l + 1 < N and A[l+1] >= A[l]:\n",
    "            l += 1\n",
    "        if l >= N-1:\n",
    "            return 0\n",
    "        while r-1 >= 0 and A[r-1] <= A[r]:\n",
    "            r -= 1\n",
    "        ans = min(N-l-1, r)\n",
    "        a = A[:l+1]\n",
    "        b = A[r:]\n",
    "        for i in range(l+1):\n",
    "            v = A[i]\n",
    "            j = bisect.bisect_left(b, v)\n",
    "            sublen = i+1 + len(b)-j\n",
    "            ans = min(ans, N-sublen)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        left_idx = -1; right_idx = n\n",
    "        for idx in range(1, n):\n",
    "            if arr[idx] < arr[idx-1]:\n",
    "                left_idx = idx\n",
    "                break\n",
    "        if left_idx == -1:\n",
    "            return 0\n",
    "\n",
    "        max_l = left_idx\n",
    "        for idx in range(n-2, -1, -1):\n",
    "            if arr[idx] > arr[idx+1]:\n",
    "                right_idx = idx + 1\n",
    "                break\n",
    "        \n",
    "        max_l = max(max_l, n - right_idx)\n",
    "        def binary(arr, start, target):\n",
    "            left, right = start, len(arr) - 1\n",
    "            while left <= right:\n",
    "                mid = left + (right-left) // 2\n",
    "                if arr[mid] >= target:\n",
    "                    right = mid - 1\n",
    "                else:\n",
    "                    left = mid + 1\n",
    "            return left\n",
    "\n",
    "        ans = float(\"inf\")\n",
    "        for i in range(left_idx):\n",
    "            idx = binary(arr, right_idx, arr[i])\n",
    "            max_l = max(max_l, n - (idx - i - 1))\n",
    "        return n - max_l\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)  \n",
    "        for r in range(n-1, -1, -1):\n",
    "            if r == 0  or arr[r-1] > arr[r]:\n",
    "                break  \n",
    "        if r == 0:\n",
    "            return 0  \n",
    "        \n",
    "        res = r  \n",
    "        for l in range(n):\n",
    "            if l>0 and arr[l] < arr[l-1]:\n",
    "                break  \n",
    "            while r<n and arr[l] > arr[r]:\n",
    "                r += 1\n",
    "            res = min(res, r-l-1)  \n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        j = n - 1\n",
    "        while j > 0 and arr[j] >= arr[j - 1]:\n",
    "            j -= 1\n",
    "        if j == 0:\n",
    "            return 0\n",
    "        #先假设需要全部删除再通过左指针维护\n",
    "        ans = j\n",
    "        for i in range(n):  \n",
    "            #判断左侧末尾与右侧首大小关系是否需要扩展区间\n",
    "            while j < n and arr[j] < arr[i]:\n",
    "                j += 1\n",
    "            ans = min(ans, j - i - 1)\n",
    "            if i + 1 < n and arr[i] > arr[i+1]:\n",
    "                break\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        j = n - 1\n",
    "        while j > 0 and arr[j - 1] <= arr[j]:\n",
    "            j -= 1\n",
    "        if j == 0:\n",
    "            return 0\n",
    "            \n",
    "        res = j\n",
    "        for i in range(n):\n",
    "            while j < n and arr[j] < arr[i]:\n",
    "                j += 1\n",
    "            res = min(res, j - i - 1)\n",
    "            if i + 1 < n and arr[i] > arr[i + 1]:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n=len(arr)\n",
    "        left=0\n",
    "        right=n-1\n",
    "        while right and arr[right-1]<=arr[right]:\n",
    "            right-=1\n",
    "        while left<n-1 and arr[left]<=arr[left+1]:\n",
    "            left+=1\n",
    "        if left>=right:\n",
    "            return 0\n",
    "        res=min(n-left-1,right)\n",
    "        right_=right\n",
    "        for l in range(left+1):\n",
    "            while right_<n and arr[right_]<arr[l]:\n",
    "                right_+=1\n",
    "            res=min(res,right_-l-1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        right = n-1\n",
    "        while right and nums[right - 1] <= nums[right]:  # 保证right后面部分有序\n",
    "            right -= 1\n",
    "        if right == 0:\n",
    "            return 0\n",
    "        res = right  # 表示删除nums[:right]使剩余数组有序\n",
    "        left = 0\n",
    "        while left == 0 or nums[left-1] <= nums[left]:\n",
    "            while right < n and nums[right] < nums[left]:\n",
    "                right += 1\n",
    "            left += 1\n",
    "            res = min(res,right - left)\n",
    "        return res\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def findLengthOfShortestSubarray(self,arr):\n",
    "        n = len(arr)\n",
    "        left, right = 0, n - 1\n",
    "\n",
    "        # 找到需要删除的前缀\n",
    "        while left < n - 1 and arr[left] <= arr[left + 1]:\n",
    "            left += 1\n",
    "\n",
    "        # 如果整个数组都是非递减的，直接返回0\n",
    "        if left == n - 1:\n",
    "            return 0\n",
    "\n",
    "        # 找到需要删除的后缀\n",
    "        while right > 0 and arr[right] >= arr[right - 1]:\n",
    "            right -= 1\n",
    "\n",
    "        # 删除中间部分的元素\n",
    "        result = min(n - left - 1, right)\n",
    "\n",
    "        # 对于剩下的前缀和后缀，找到需要删除的元素\n",
    "        i, j = 0, right\n",
    "        while i <= left and j < n:\n",
    "            if arr[i] <= arr[j]:\n",
    "                result = min(result, j - i - 1)\n",
    "                i += 1\n",
    "            else:\n",
    "                j += 1\n",
    "\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        left = 0\n",
    "        right = n-1\n",
    "        while (left<(n-1)) and (arr[left]<=arr[left+1]):\n",
    "            left += 1\n",
    "        while (right>=0) and (arr[right]>=arr[right-1]):\n",
    "            right -= 1\n",
    "        ans = min(right,n-left-1)\n",
    "        if left>=right:\n",
    "            return 0\n",
    "        r = right\n",
    "        for l in range(left+1):\n",
    "            while r<n and arr[r]<arr[l]:\n",
    "                r += 1\n",
    "            ans = min(ans,r-l-1)\n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        right = n - 1\n",
    "        while right and arr[right - 1] <= arr[right]:\n",
    "            right -= 1\n",
    "        if right == 0:  # arr 已经是非递减数组\n",
    "            return 0\n",
    "        # 此时 arr[right-1] > arr[right]\n",
    "        ans = right  # 删除 arr[:right]\n",
    "        left = 0  # 枚举 left\n",
    "        while left == 0 or arr[left - 1] <= arr[left]:\n",
    "            while right < n and arr[right] < arr[left]:\n",
    "                right += 1\n",
    "            # 此时 arr[left] <= arr[right]，删除 arr[left+1:right]\n",
    "            ans = min(ans, right - left - 1)\n",
    "            left += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        j = n - 1\n",
    "        while j > 0 and arr[j-1] <= arr[j]:\n",
    "            j -= 1\n",
    "        if j == 0:\n",
    "            return 0\n",
    "        res = j\n",
    "        for i in range(n):\n",
    "            while j < n and arr[j] < arr[i]:\n",
    "                j +=1\n",
    "            res = min(res,j - i - 1)\n",
    "            if i + 1 < n and arr[i] > arr[i+1]:\n",
    "                break\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        right = n - 1\n",
    "        while right and arr[right - 1] <= arr[right]:\n",
    "            right -= 1\n",
    "        if right == 0:  # arr 已经是非递减数组\n",
    "            return 0\n",
    "        # 此时 arr[right-1] > arr[right]\n",
    "        ans = right  # 删除 arr[:right]\n",
    "        left = 0  # 枚举 left\n",
    "        while left == 0 or arr[left - 1] <= arr[left]:\n",
    "            while right < n and arr[right] < arr[left]:\n",
    "                right += 1\n",
    "            # 此时 arr[left] <= arr[right]，删除 arr[left+1:right]\n",
    "            ans = min(ans, right - left - 1)\n",
    "            left += 1\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "\n",
    "        if n <= 1:\n",
    "            return 0\n",
    "\n",
    "        # 查找左边递增序列的索引范围\n",
    "        left_start = 0\n",
    "        left_end = n - 1\n",
    "        for i in range(1, n):\n",
    "            if arr[i] >= arr[i - 1]:\n",
    "                continue\n",
    "            else:\n",
    "                left_end = i - 1\n",
    "                break\n",
    "        if left_end == n - 1:\n",
    "            # 已经是非递减了\n",
    "            return 0\n",
    "        elif left_end == n - 2:\n",
    "            # 只差1个\n",
    "            return 1\n",
    "        \n",
    "        # 查找右边递增序列的索引范围\n",
    "        right_end = n - 1\n",
    "        right_start = left_end + 1\n",
    "        for i in range(n-2, left_end, -1):\n",
    "            if arr[i] <= arr[i + 1]:\n",
    "                continue\n",
    "            else:\n",
    "                right_start = i + 1\n",
    "                break\n",
    "        if right_start == 1:\n",
    "            # 只差1个\n",
    "            return 1\n",
    "\n",
    "        if arr[left_end] <= arr[right_start]:\n",
    "            # 只需移除中间的\n",
    "            return right_start - left_end - 1\n",
    "        elif arr[left_start] > arr[right_end]:\n",
    "            return n - max(left_end - left_start + 1, right_end - right_start + 1)\n",
    "\n",
    "        \n",
    "        # 剩下情况如下     rightend\n",
    "        #  leftend        /\n",
    "        #    /           /\n",
    "        #   /           /\n",
    "        #  /            rightstart\n",
    "        # leftstart    \n",
    "        result = n - (right_end - right_start + 1)  # 左边序列都不保留时\n",
    "        left_index = left_start\n",
    "        right_index = right_start\n",
    "        while left_index <= left_end:\n",
    "            # 左边保留到 left_index 时\n",
    "            # 右边应该保留到 right_index\n",
    "            while right_index <= right_end and arr[left_index] > arr[right_index]:\n",
    "                right_index += 1\n",
    "            \n",
    "            r = right_index - left_index - 1\n",
    "            if r < result:\n",
    "                result = r\n",
    "                \n",
    "            left_index += 1\n",
    "        return result\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "\n",
    "        if n <= 1:\n",
    "            return 0\n",
    "\n",
    "        # 查找左边递增序列的索引范围\n",
    "        left_start = 0\n",
    "        left_end = n - 1\n",
    "        for i in range(1, n):\n",
    "            if arr[i] >= arr[i - 1]:\n",
    "                continue\n",
    "            else:\n",
    "                left_end = i - 1\n",
    "                break\n",
    "        if left_end == n - 1:\n",
    "            # 已经是非递减了\n",
    "            return 0\n",
    "        elif left_end == n - 2:\n",
    "            # 只差1个\n",
    "            return 1\n",
    "        \n",
    "        # 查找右边递增序列的索引范围\n",
    "        right_end = n - 1\n",
    "        right_start = left_end + 1\n",
    "        for i in range(n-2, left_end, -1):\n",
    "            if arr[i] <= arr[i + 1]:\n",
    "                continue\n",
    "            else:\n",
    "                right_start = i + 1\n",
    "                break\n",
    "        if right_start == 1:\n",
    "            # 只差1个\n",
    "            return 1\n",
    "\n",
    "        if arr[left_end] <= arr[right_start]:\n",
    "            # 只需移除中间的\n",
    "            return right_start - left_end - 1\n",
    "        elif arr[left_start] > arr[right_end]:\n",
    "            return n - max(left_end - left_start + 1, right_end - right_start + 1)\n",
    "\n",
    "        \n",
    "        # 剩下情况如下     rightend\n",
    "        #  leftend        /\n",
    "        #    /           /\n",
    "        #   /           /\n",
    "        #  /            rightstart\n",
    "        # leftstart    \n",
    "        result = n - (right_end - right_start + 1)  # 左边序列都不保留时\n",
    "        left_index = left_start\n",
    "        right_index = right_start\n",
    "        while left_index <= left_end:\n",
    "            # 左边保留到 left_index 时\n",
    "            while right_index <= right_end and arr[left_index] > arr[right_index]:\n",
    "                right_index += 1\n",
    "            \n",
    "            r = right_index - left_index - 1\n",
    "            if r < result:\n",
    "                result = r\n",
    "                \n",
    "            left_index += 1\n",
    "        return result\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "\n",
    "        n = len(arr)\n",
    "        d = {}\n",
    "\n",
    "        # 1,2,3,10,4,8,5\n",
    "\n",
    "        l = n\n",
    "        for i in range(1, n):\n",
    "            if arr[i] < arr[i-1]:\n",
    "                l = i\n",
    "                break\n",
    "\n",
    "\n",
    "        st = [(inf, n)]\n",
    "        for i in range(n-1, l, -1):\n",
    "\n",
    "            if arr[i] <= st[-1][0]:\n",
    "                if arr[i] == st[-1][0]:\n",
    "                    st[-1][1] = i\n",
    "                else:\n",
    "                    st.append([arr[i], i])\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        #print(f'{st} {l}')\n",
    "        ret = st[-1][1]\n",
    "        for i in range(l):\n",
    "            while st[-1][0] < arr[i]:\n",
    "                st.pop()\n",
    "            \n",
    "            delete_num = st[-1][1] - 1 - i\n",
    "            #print(f'{st} {delete_num}')\n",
    "            ret = min(ret, delete_num)\n",
    "        \n",
    "        return ret\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        result = n\n",
    "        #删后\n",
    "        left = n-1\n",
    "        flag = False\n",
    "        for i in range(1,n):\n",
    "            if(arr[i-1] > arr[i]):\n",
    "                flag = True\n",
    "                break\n",
    "        if(flag):\n",
    "            left = i - 1\n",
    "        result = min(result, n - left - 1)\n",
    "        #删前\n",
    "        right = 0\n",
    "        flag = False\n",
    "        for i in range(n-1,0,-1):\n",
    "            if(arr[i-1] > arr[i]):\n",
    "                flag = True\n",
    "                break\n",
    "        if(flag):\n",
    "            right = i\n",
    "        result = min(result, right)\n",
    "        j = right\n",
    "        for i in range(left+1):\n",
    "            while(j <= i or (j <= n- 1 and arr[j] < arr[i])):\n",
    "                j += 1\n",
    "            if(j < n):\n",
    "                result = min(result, j-i-1)\n",
    "        return result\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "        right = n - 1\n",
    "        while right and arr[right - 1] <= arr[right]:\n",
    "            right -= 1\n",
    "        if not right:\n",
    "            return 0\n",
    "        # 有可能后缀才是符合条件的答案\n",
    "        ans = right\n",
    "        left = 0\n",
    "        while left == 0 or arr[left - 1] <= arr[left]:\n",
    "            # 核心代码：对于前缀的每一个元素，如果都无法跟后缀拼接，那就将后缀缩小。\n",
    "            while right < n and arr[right] < arr[left]:\n",
    "                right += 1\n",
    "            ans = min(ans, right - left - 1)\n",
    "            left += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findLengthOfShortestSubarray(self, arr: List[int]) -> int:\n",
    "        n = len(arr)\n",
    "\n",
    "        if n <= 1:\n",
    "            return 0\n",
    "\n",
    "        # 查找左边递增序列的索引范围\n",
    "        left_start = 0\n",
    "        left_end = n - 1\n",
    "        for i in range(1, n):\n",
    "            if arr[i] >= arr[i - 1]:\n",
    "                continue\n",
    "            else:\n",
    "                left_end = i - 1\n",
    "                break\n",
    "        if left_end == n - 1:\n",
    "            # 已经是非递减了\n",
    "            return 0\n",
    "        elif left_end == n - 2:\n",
    "            # 只差1个\n",
    "            return 1\n",
    "        \n",
    "        # 查找右边递增序列的索引范围\n",
    "        right_end = n - 1\n",
    "        right_start = left_end + 1\n",
    "        for i in range(n-2, left_end, -1):\n",
    "            if arr[i] <= arr[i + 1]:\n",
    "                continue\n",
    "            else:\n",
    "                right_start = i + 1\n",
    "                break\n",
    "        if right_start == 1:\n",
    "            # 只差1个\n",
    "            return 1\n",
    "\n",
    "        if arr[left_end] <= arr[right_start]:\n",
    "            # 只需移除中间的\n",
    "            return right_start - left_end - 1\n",
    "        elif arr[left_start] > arr[right_end]:\n",
    "            return n - max(left_end - left_start + 1, right_end - right_start + 1)\n",
    "\n",
    "        \n",
    "        # 剩下情况如下     rightend\n",
    "        #  leftend        /\n",
    "        #    /           /\n",
    "        #   /           /\n",
    "        #  /            rightstart\n",
    "        # leftstart    \n",
    "        result = n - (right_end - right_start + 1)  # 左边序列都不保留时\n",
    "        left_index = left_start\n",
    "        right_index = right_start\n",
    "        while left_index <= left_end:\n",
    "            # 左边保留到 left_index 时\n",
    "            while right_index <= right_end and arr[left_index] > arr[right_index]:\n",
    "                right_index += 1\n",
    "            \n",
    "            r = right_index - left_index - 1\n",
    "            if r < result:\n",
    "                result = r\n",
    "                \n",
    "            left_index += 1\n",
    "        return result\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
